501D - Misha and Permutations Summation - CodeForces Solution

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 523232, lg=18;
const ll MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=MOD)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = getmod(ans*a);
        b >>= 1;
        a = getmod(a*a);
    }
    return ans;
}

int n, A[N], P[N], Q[N], ANS[N], seg[N];

void reset() {
	for(int i=(1<<lg);i<=(1<<lg+1)-1;i++) {
		seg[i] = 1;
	}
	for(int i=(1<<lg)-1; i; --i) {
		seg[i] = seg[2*i] + seg[2*i+1];
	}
}

void update(int ind) {
	if(ind==0) {return;}
	if(ind>=(1<<lg)) {
		seg[ind] = 0;
	} else {
		seg[ind] = seg[2*ind] + seg[2*ind+1];
	}
	update(ind/2);
}

int query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(l>=rc || lc>=r) {return 0;}
	if(l<=lc && rc<=r) {
		return seg[ind];
	}
	int mid = (rc+lc)/2;
	return query(l, r, 2*ind, lc, mid) + query(l, r, 2*ind+1, mid, rc);
}

int query2(int wh, int ind=1) {
	if(ind>=(1<<lg)) {
		return (ind-(1<<lg)+1);
	}
	if(seg[2*ind]>=wh) {return query2(wh, 2*ind);}
	return query2(wh-seg[2*ind], 2*ind+1);
}

int main () {
	ios;

	cin>>n;
	reset();
	for(int i=1; i<=n; i++) {
		cin>>P[i]; P[i]++;
		A[n-i] += query(1, P[i]);
		update(P[i]+(1<<lg)-1);
	}
	reset();
	for(int i=1; i<=n; i++) {
		cin>>Q[i]; Q[i]++;
		A[n-i]+=query(1, Q[i]);
		update(Q[i]+(1<<lg)-1);
	}
	reset();
	for(int i=1;i<=n;i++) {
		if(A[i]>i) {A[i]-=(i+1); A[i+1]++;}
	}
	for(int i=n-1;i>=0;i--) {
		ANS[n-i] = query2(A[i]+1);
		update(ANS[n-i]+(1<<lg)-1);
	}
	for(int i=1; i<=n; ++i) {
		cout<<ANS[i]-1<<' ';
	}

	return 0;
}